package b_tree;

public class bTree {

    class bTreeNode {
        int[] keys;
        int usedSize;
        bTreeNode[] childs;
        bTreeNode parent;

        public bTreeNode() {
            keys = new int[M];
            childs = new bTreeNode[M + 1];
        }
    }

    public static final int M = 3;

    bTreeNode root;

    public boolean insert(int val) {
        //B树为空,直接插入
        if (root == null) {
            root = new bTreeNode();
            root.keys[0] = val;
            root.usedSize++;
            return true;
        }
        //B树不为空
        //判断树里有没有这个值
        Pair<bTreeNode, Integer> pair = findVal(val);
        //根据value值判断这个值是不是在树中

        if (pair.getValue() != -1) {
            //等于-1,不存在该值
            //不等于,存在该值
            //存在该值无法进行插入,退出返回false
            return false;
        }
        bTreeNode parent = pair.getKey();
        //进行插入
        int index = parent.usedSize - 1;
        while (index >= 0) {
            if (val < parent.keys[index]) {
                parent.keys[index + 1] = parent.keys[index];
            } else {
                //大于情况,等于已经在find判断过了
                break;
            }
            index--;
        }
        parent.keys[index + 1] = val;
        parent.usedSize++;
        if (parent.usedSize >= M) {
            split(parent);
        }
        return true;
    }


    /**
     * 表示当前要分裂的节点
     *
     * @param sNode
     */
    private void split(bTreeNode sNode) {
        bTreeNode newNode = new bTreeNode();
        bTreeNode psNode = sNode.parent;
        //分裂节点的父节点
        //对分裂节点区域进行划分
        int i = 0;
        int mid = sNode.usedSize / 2;
        int j = mid + 1;
        while (j < sNode.usedSize) {
            newNode.keys[i] = sNode.keys[j];
            newNode.childs[i] = sNode.childs[j];
            //分裂节点孩子节点在转移的时候要修改他们的父结点
            if (sNode.childs[i] != null) {
                sNode.childs[i].parent = newNode;
            }
            j++;
            i++;
        }
        //将最后一个孩子节点记录下来,重复一次
        newNode.childs[i] = sNode.childs[j];
        if (sNode.childs[i] != null) {
            sNode.childs[i].parent = newNode;
        }
        newNode.usedSize = i;
        //更新原来节点的有效数据数量
        //减去右侧数据的数量,再减去中间数据,因为中间数据要被提到分裂节点的父结点中去
        sNode.usedSize = sNode.usedSize - i - 1;
        //更新新节点的父亲节点和有效数据数量
        if (sNode == root) {
            root = new bTreeNode();
            root.keys[0] = sNode.keys[mid];
            root.childs[0] = sNode;
            root.childs[1] = newNode;
            sNode.parent = root;
            newNode.parent = root;
            root.usedSize = 1;
            return;
        }

        newNode.parent = psNode;

        //将分裂节点的中间值提到父亲节点
        int fIndexEnd = psNode.usedSize - 1;
        //中间值
        int midValue = sNode.keys[mid];

        while (fIndexEnd >= 0) {
            if (sNode.parent.keys[fIndexEnd] > midValue) {
                sNode.parent.keys[fIndexEnd + 1] = sNode.parent.keys[fIndexEnd];
                sNode.parent.childs[fIndexEnd + 2] = sNode.parent.childs[fIndexEnd + 1];
            } else {
                break;
            }
            fIndexEnd--;
        }
        psNode.keys[fIndexEnd + 1] = midValue;
        psNode.childs[fIndexEnd + 2] = newNode;
        psNode.usedSize++;
        if (psNode.usedSize >= M) {
            split(psNode);
        }
    }

    private Pair<bTreeNode, Integer> findVal(int val) {
        bTreeNode cur = root;
        bTreeNode parent = null;
        while (cur != null) {
            int i = 0;

            while (i < cur.usedSize) {
                if (cur.keys[i] == val) {
                    return new Pair<>(cur, i);
                } else if (cur.keys[i] < val) {
                    i++;
                } else {
                    break;
                }
            }
            parent = cur;
            cur = cur.childs[i];
        }
        return new Pair<>(parent, -1);
    }

    public static void main(String[] args) {
        bTree myBtree = new bTree();
        int[] array = {53, 139, 75, 49, 145, 36,101};
        for (int i = 0; i < array.length; i++) {
            myBtree.insert(array[i]);
        }
        System.out.println("fdsafafa");
        myBtree.inorder(myBtree.root);
    }
    private void inorder(bTreeNode root){
        if(root == null)
            return;
        for(int i = 0; i < root.usedSize; ++i){
            inorder(root.childs[i]);
            System.out.println(root.keys[i]);
        }
        inorder(root.childs[root.usedSize]);
    }
}


